package need_learn.coding.meituan;

import java.util.TreeSet;

/**
 * TODO 美团，数组合并去重 升序输出  已使用 TreeSet 解决， 考虑有别的解法？
 * 必须掌握。。。。。。。。。别的方法
 *
 * @author david
 * @version 1.0
 * @date 2021/4/20 14:56
 */
public class MergeArray {
    public static void main(String[] args) {
        int[] num1 = {1, 3, 5};
        int[] num2 = {2, 4, 6, 7, 8};
//        int[] ints = merge(num1, num2);
        Integer[] ints = mergeTreeSet(num1, num2);
        for (int i : ints) {
            System.out.println(i);
        }

    }

    public static Integer[] mergeTreeSet(int [] num1, int[] num2){
        int[] ints =new int[num1.length+num2.length];
        TreeSet<Integer> intSets=new TreeSet<>();
        for (int i:num1){
            intSets.add(i);
        }
        for (int j:num2){
            intSets.add(j);
        }
        return intSets.toArray(new Integer[]{});
    }
    //给定两个有序整数数组nums和num2，合并为一个排序数组
    public static int[] merge(int[] num1, int[] num2) {
        int i = num1.length - 1;
        int j = num2.length - 1;
        //合并后最后一个数的索引为m+n-1
        int k = num1.length + num2.length - 1;
        //实际创建数组应该是索引加一的大小
        int[] ints = new int[k + 1];
        while (i >= 0 && j >= 0) {
            //将两个数组中从最后一位开始比较，较大的先插入
            //当j先等于0时，说明num2的数字已经全部复制到num1中，此时合并完成(说明num1中最小的元素比num2小)
            //当i先等于0时，说明num1中原来的所有数字已经复制完毕，此时进入下面的循环(说明num1中最小的元素比num2大)
            ints[k--] = num1[i] > num2[j] ? num1[i--] : num2[j--];
        }
        while (j >= 0) {
            ints[k--] = num2[j--];
        }
        while (i >= 0) {
            ints[k--] = num1[i--];
        }
        return ints;
    }
}
